Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Звіт
до лабораторної роботи №1
з дисципліни “Моделювання систем”
ДОСЛІДЖЕННЯ РОЗІМКНУТИХ СТОХАСТИЧНИХ АНАЛІТИЧНИХ МОДЕЛЕЙ
ОБЧИСЛЮВАЛЬНИХ СИСТЕМ (ОС)
Мета роботи: вивчити методи розрахунку розімкнутих стохастичних мережних моделей ОС, які ґрунтуються на представленні обчислювального процесу марківським випадковим процесом.
Теоретичні відомості
Можливість інтерпретації роботи ОС стохастичними мережами основана на модульності побудови сучасних обчислювальних засобів, функціональної незалежності модулів і паралельній їх роботі.
Будемо розглядати обчислювальний процес (ОП) як послідовність етапів рахунку і вводу-виводу інформації при звернені до файлів F1,...,Fn, пов’язаних з конкретною реалізацією задачі. Типова діаграма такого процесу показана на рис. 1.
Рис. 1. Граф марківського ланцюга, що є моделлю обчислювального процесу: P0,i - ймовірності переходів:
Стан ОП, що відповідає етапу рахунку, який позначений символом Е0, а стан, що відповідає зверненню до файлів F1,...,Fn, - символами Е,...,Еn. Закінчення обчислювального процесу розглядається як перехід процесу в стан Еn+1,що поглинає ОП. В цих позначеннях ОП - це послідовність станів Еt0,Et1,...,Etn, що змінюються в моменти часу t0,t2,...,tn, причому Eti({E1,...,En} і заключний стан процесу Etn=En+1.
Властивість марківської моделі ОП заключається в тому, що приймається допущення про відсутність післядії ОП, яка означає, що наступні стани ОП залежать тільки від біжучого його стану і не залежать від попередніх.
Рис.2. Розімкнута стохастична мережна модель ОС
Відображаючи множину станів ОП на множину модулів ОС (процесори, канали вводу- виводу (КВВ), пристрої вводу-виводу (ПВВ)), з якими пов’язане обслуговування ОП в цих станах, приходимо до наступної мережної моделі ОС (рис.2).Модулі ОС представляються системами масового обслуговування (СМО). Стан Е0 ототожнюється з роботою процесора (ПР), стани Еі - з роботою ПВВ і КВВ. На рисунку 2 P1,i відповідають P0,i-1 рис.1.
Передбачається, що файл Fi знаходиться на ПВВ . Коли декілька файлів знаходяться на одному ПВВ, ймовірність звернення до цього пристрою дорівнює сумі ймовірності звернень до розташованих на ньому файлів. Наприклад, на ПВВ3 розташовані файли F5, F6, F10, з цього випливає, що P1,3=P0,5+P0,6+P0,10.
Зображена на рис.2 стохастична модель ОС представляє собою розімкнуту мережу. Особливість такої моделі заключається в тому, що в ній одночасно можуть існувати змінна кількість активних ОП, конкуруючих за захоплення ресурсів ОС. Процес розв`язку задачі полягає в послідовному обслуговуванні відповідної заявки, що циркулює в мережі СМО. В данних методичних вказівках розглядаються експоненціальні мережі, для яких існують точні аналітичні розв’язки. Для них характерним є експоненціальний розподіл часу обслуговування СМО мережі і найпростіший вхідний потік заявок з інтенсивністю .
Розімкнута стохастична мережа визначається наступною сукупністю параметрів:
1) числом N СМО S1,..., SN (ПР,ПВВ,КВВ), що утворюють мережу (див. рис.2);
2) числом каналів (пристроїв, що обслуговують) К1,...,КN, що входять в системи S1,..., SN;
3) матрицею ймовірностей передач Р=[Pij], де Pij - ймовірність того, що заявка, яка залишає систему Si, поступить в систему Sj(i,j=0,N);
4) інтенсивністю джерела заявок S0, що визначає кількість генеруємих задач;
5) середніми тривалостями обслуговування заявок V1,...VN в системах S1,..., SN.
При розрахунку мережі знаходяться ймовірності станів мережі Pr(M1,...,MN), де Мi - кількість заявок в системі Si, а також, що визначаються на їх основі, середні довжини черг заявок l1,...,lN, що очікують обслуговування в системах S1,...,SN, середнє ...